#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;char C=getchar();
    while(C<'0'||C>'9'){if(C=='-')f=-1;C=getchar();}
    while(C>='0'&&C<='9')x=x*10+(C^48),C=getchar();
    return x*f;
}
inline void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>=10)write(x/10);
    putchar(x%10+'0');
}
const int N = 2000+5;
int n,a[N];
int f[N][2][N];
void solve(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            f[i][0][1]=max(f[i][0][1],f[j][1][i-j]+(a[i]==a[j-1])*a[i]);
            f[i][1][1]=max(f[i][1][1],f[j][0][i-j]+(a[i]==a[j-1])*a[i]);
        }
        for(int k=2;i+k-1<=n;k++){
            f[i][0][k]=f[i][0][k-1]+(a[i+k-2]==a[i+k-1])*a[i+k-2];
            f[i][1][k]=f[i][1][k-1]+(a[i+k-2]==a[i+k-1])*a[i+k-2];
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,max(f[i][0][n-i+1],f[i][1][n-i+1]));
    }
    cout<<ans<<endl;
}
signed main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    int T=read();
    while(T--){
        solve();
    }
    return 0;
}